package airthmetic.exercise.tree;

import java.util.*;

public class _515_在每个树行中找最大值 {
    // DFS
    public List<Integer> largestValues(TreeNode root) {
        if(root == null){
            return new ArrayList<Integer>();
        }
        Map<Integer,Integer> cache = new HashMap();
        List<Integer> res = new ArrayList();
        recur(root,cache,0);
        for(Integer key:cache.keySet()){
            res.add(key,cache.get(key));
        }
        return res;

    }

    public void recur(TreeNode root, Map<Integer,Integer> cache,int level){
        if(root == null){
            return;
        }
        if(cache.get(level) == null){
            cache.put(level,root.val);
        }else{
            Integer max = cache.get(level);
            if(root.val > max){
                cache.put(level,root.val);
            }
        }

        recur(root.left,cache,level+1);
        recur(root.right,cache,level+1);
    }

    // BFS
    public List<Integer> largestValues2(TreeNode root) {
        if(root == null){
            return new ArrayList<Integer>();
        }
        Queue<TreeNode> queue = new LinkedList();
        List<Integer> res = new ArrayList();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            int max = Integer.MIN_VALUE;
            for(int i=0; i<size; i++){
                TreeNode n = queue.poll();
                if(n.left != null){
                    queue.offer(n.left);
                }
                if(n.right != null){
                    queue.offer(n.right);
                }

                max = Math.max(max, n.val);
            }

            res.add(max);
        }
        return res;

    }
}
